Many servers, such as web and database servers, receive a continual stream of job requests requiring vastly different amounts of processing time. The processing times of different jobs can vary over several orders of magnitude. These times can depend, in part, on whether the server system utilizes a non-pre-emptive setting, in which jobs are processed without interruption, or a pre-emptive setting, in which jobs may be suspended and later resumed. In both the pre-emptive and non-pre-emptive cases, though most particularly in the pre-emptive case, each server must produce a schedule which services the continual stream of job requests in the most efficient and "fair" way possible. There are various ways to gauge the efficiency and fairness of a schedule, such as throughput, avoiding jitter, etc., but one indication of fairness is the widely-accepted requirement that the schedule be responsive to each job and avoid starvation of any job.
In order to produce a schedule that optimizes the scheduling of job requests made of a server, several strategies utilizing scheduling metrics, are typically used. Two classical optimization metrics in scheduling theory are makespan and average completion time. The makespan is a suitable measure for batched jobs, and average completion time is useful in some compiler optimization settings. However, neither of these is a suitable measure when jobs arrive in a continuous stream. For jobs arriving continuously, the sum-flow has been considered for the past two decades to be the suitable metric for optimization. The relevant parameter of the sum-flow metric is the time a job spends in the system. The sum-flow metric sums the time all jobs spend in the system. This optimization scheme is the basis for the Shortest Remaining Process Time (hereinafter "SRPT") heuristic, which produces a schedule which minimizes the time it takes to process all of the uncompleted jobs in the system when there is a single processor.
However, as is well known in the industry, the SRPT heuristic has the drawback that it leads to starvation. Starvation occurs when some job request to the server is delayed to an unbounded extent. Although the SRPT heuristic can be desirable in some circumstances, the fact that specific job requests are delayed to an unbounded extent is unfair to the person who made the request which is delayed. Furthermore, the fact that some job requests are delayed to an unbounded extent prevents the owner of the server system from being able to make a quality-of-service guarantee to each user that the schedule will be responsive to each job and avoid starvation of any job.
Therefore, a need exists for a server system which optimizes the scheduling of a continuous stream of jobs request and provides the "fairest" possible service to users, enabling the owner of the server to make a quality-of-service guarantee to each user that the schedule will be responsive to each job and avoid starvation of any job.